#include <iostream>
#include <vector>

using namespace std;

/*
Given a set of schedule with start time and end time pair. Mark the pairs that have conflicts with others.

Time complexity O(nlgn)
*/

class Schedule
{
public:
	int start;
	int end;
	bool IsConflict;
};

void PrintSchedule(class Schedule* schs, int n)
{
	for(int i=0; i<n; i++)
		cout<<schs[i].start<<" "<<schs[i].end<<" "<<schs[i].IsConflict<<endl;
}

void Swap( Schedule &A, Schedule &B )
{
	Schedule temp = A;
	A = B;
	B = temp;
}

void QuickSortSchedule( Schedule* A, int left, int right)
{
	int index = left;
	if(left >= right )
		return;

	for( int i= left+1; i<=right; i++)
	{
		if( A[i].start<A[left].start )
		{
			Swap( A[++index], A[i] );
		}
	}
	Swap( A[index], A[left] );

	QuickSortSchedule( A, left, index-1);
	QuickSortSchedule( A, index+1, right );
	return;
}

void ProcessSchedule( Schedule* schs, int n)
{
	if( n <= 1 )
		return;

	QuickSortSchedule( schs, 0, n-1 );
	Schedule *pre = &schs[0];
	int start = schs[0].start;
	int end = schs[0].end;
	
	for( int i=1; i<n; i++ )
	{
		if( schs[i].start<=end )
		{
			pre->IsConflict = true;
			schs[i].IsConflict = true;
			pre = (pre->end>schs[i].end)?pre:&schs[i];
			end = (pre->end>schs[i].end)?pre->end:schs[i].end;
		}
		else
		{
			pre = &schs[i];
			start = pre->start;
			end = pre->end;
		}
	}
}

int main()
{
	Schedule schs[] = {{1,5,0},{2,3,0},{5,7,0},{9,12,0},{3,4,0},{10,15,0},{33,35,0},{17,22,0},{21,25,0},{22,23,0},{24,28,0},{27,28,0},{29,30,0},{36,39,0}};
	int n = sizeof(schs)/sizeof(schs[0]);

	// in the real interview, need to validate the schedule pair 
	// to make sure end is already <= start
	ProcessSchedule( schs, n);
	PrintSchedule(schs,n);
	cout<<"Press anykey to terminate..."<<endl;
	return getchar();
}

